package Common;
/**
 *Graph.java is a class to assist with
 *graph and network algorithms for
 *CITS3210. It is assumed that the edges
 *of the graph have only positive integer
 *weights (of value 1 if the graph is not
 *weighted).
 *@author Tim French
 *@author Darren Hassan added support for labelled graphs
 **/

import java.util.HashMap;
import java.util.ArrayList;
import java.util.Random;

public class Graph{

  private int[][] edgeMatrix;
  private int numberOfVertices;
  private boolean directed;
  private boolean weighted;
  private String[] labels;
  // Node label to node index mapping
  private HashMap<String, ArrayList<Integer>> labelToPosition;
  // Node index to label mapping
  private HashMap<Integer, String> positionToLabel;

  /**
   *Constructs an graph with n vertices and no edges
   *@param vertices the number of vertices (must be greater than 0)
   *@param weighted true if the graph is to be weighted
   *@param directed true if the graph is directed
   **/
  private Graph(int vertices, boolean weighted, boolean directed){
    if(vertices<1) numberOfVertices = 0;
    else numberOfVertices = vertices;
    edgeMatrix = new int[numberOfVertices][numberOfVertices];
    labels = new String[numberOfVertices];
    this.weighted = weighted;
    this.directed = directed;
    labelToPosition = new HashMap<String, ArrayList<Integer>>();
    positionToLabel = new HashMap<Integer, String>();
  }

 /**
   *Constructs an unwieghted, undirected graph with n vertices and no edges
   *@param vertices the number of vertices (must be greater than 0)
   **/
  private Graph(int vertices){
    this(vertices, false, false);
  }

  /**
   *Adds an edge of the given weight to the graph.
   *If the graph is undirected the reverse edge is also added.
   *If the graph is unweighted the weight is set to one.
   *If an edge already exists it is overwritten with the new weight.
   *@param u the start of the edge
   *@param v the end of the edge
   *@param weight the weight of the edge
   **/
  private void addEdge(int u, int v, int weight){
    if(0<=u&&0<=v&&u<=numberOfVertices&&v<=numberOfVertices){
      if(weight<1) weight = 0;
      else if(!weighted) weight = 1;
      edgeMatrix[u][v] = weight;
      if(!directed) edgeMatrix[v][u] = weight;
    }
    else throw new RuntimeException("Vertex out of bounds");
  }

 /**
   *Adds an edge of weight 1 to the graph.
   *If the graph is undirected the reverse edge is also added.
   *@param u the start of the edge
   *@param v the end of the edge
   **/
  private void addEdge(int u, int v){
    this.addEdge(u,v,1);
  }

  /**
   *Removes the edge from the graph (sets the edge weight to 0).
   *If the graph is undirected the reverse edge is also removed.
   *@param u the start of the edge
   *@param v the end of the edge
   **/
  private void removeEdge(int u, int v){
    this.addEdge(u,v,0);
  }

  /**
   *@return the weight of an edge.
   *@param u the start of the edge
   *@param v the end of the edge
   **/
  public int getWeight(int u, int v){
    if(0<=u&&0<=v&&u<=numberOfVertices&&v<=numberOfVertices)
      return edgeMatrix[u][v];
    else throw new RuntimeException("Vertex out of bounds");
  }

  /**
   *@return the number of vertices
   **/
  public int getNumberOfVertices(){
    return numberOfVertices;
  }

  /**
   *@return true if the graph is directed
   **/
  public boolean isDirected(){
    return directed;
  }

  /**
   *@return true if the graph is weighted
   **/
  public boolean isWeighted(){
    return weighted;
  }

  /**
   *@return a clone of the edgeMatrix
   **/
  public int[][] getEdgeMatrix(){
	int[][] clone = new int[edgeMatrix.length][edgeMatrix.length];
	for(int i = 0; i<edgeMatrix.length; i++)
		clone[i] = (int[])edgeMatrix[i].clone();
	return clone;
  }

  /**
   * A mutator for the label array and label to position HashMap
   * The label at index 0 in the label array is the label of node 0 etc
   *
   * @param i The node index of which the label belongs to
   * @param l A label to add to the array of labels
   */
  private void addLabel(int i, String l) {
	labels[i] = l;

	// Instantiate the list of positions
	ArrayList<Integer> list = new ArrayList<Integer>();

	// Test if the pattern is a repeat
	if (labelToPosition.containsKey(l)){
		// Find the list of previous positions this pattern has been found
		list.addAll(this.labelToPosition.get(l));
		//	Add this position to the end of the list
		list.add(Integer.valueOf(i));
	}
	else {
		// Add this position to a new list, this is the first time this
		// pattern has been found
		list.add(Integer.valueOf(i));
	}
	// Create a mapping from this pattern to the list of positions its been found
	this.labelToPosition.put(l, list);
	// Create a mapping from this position to label
	this.positionToLabel.put(i, l);
  }

  /**
   * Get an array of labels where the index corresponds to the node index
   * the label belongs to
   *
   * @return the label array
   */
  public String[] getLabels() {
	  return labels;
  }

  /**
   * Get the label of a particular node
   *
   * @param i the node index to find the label of
   * @return the label of the node
   */
  public String getLabelAt(int i) {
	  return positionToLabel.get(Integer.valueOf(i));
  }

  /**
   * Does the set of labels for the graph contain a given symbol
   *
   * @param l the symbol to test
   * @return True - the symbol matches one of the labels of the graph
   * 		 False - otherwise
   */
  public boolean contains(String l) {
	  return this.labelToPosition.containsKey(l);
  }

  /**
   * Get the nodes that has a particular label
   *
   * @param l the label
   * @return a list of node that have that label
   */
  public ArrayList<Integer> getIndexOf(String l) {
	  return this.labelToPosition.get(l);
  }

  /**
   *Creates a random unweighted graph
   *@return a random graph of the specified density
   *@param numberOfVertices the number of vertices
   *@param directed true if the graph is to be directed
   *@param density between 0 and 1, the probability of an edge existing.
   **/
  public static Graph randomGraph(int numberOfVertices, boolean directed, double density){

    Graph g = new Graph(numberOfVertices, false, directed);
    for(int i = 0; i<g.getNumberOfVertices(); i++){
      for(int j = 0; j<(directed?g.getNumberOfVertices():i+1); j++){
	if(Math.random()<density){
	  g.edgeMatrix[i][j] = 1;
	  if(!directed) g.edgeMatrix[j][i] = 1;
	}
      }
    }
    return g;
  }

  /**
   *Creates a random unweighted, undirected graph
   *@return a random graph of the specified density
   *@param numberOfVertices the nukmber of vertices
   *@param directed true if the graph is to be directed
   *@param density between 0 and 1, the probablity of an edge existing.
   **/
  public static Graph randomGraph(int numberOfVertices, double density){
    return randomGraph(numberOfVertices, false, density);
  }

  /**
   * Creates a random unweighted, directed graph with random
   * labels from specified available labels.
   *
   * @param numberOfVertices the number of vertices
   * @param density between 0 and 1, the probablity of an edge existing
   * @param labels specified available labels
   * @return
   */
  public static Graph randomGraph(int numberOfVertices, double density, String[] labels) {

	  Graph g = randomGraph(numberOfVertices, true, density);

	  Random r = new Random(System.currentTimeMillis());

	  // Add random labels to nodes
	  for(int i = 0; i < numberOfVertices; i++) {

		  g.addLabel(i, labels[r.nextInt(labels.length)]);
	  }

	  return g;
  }

  /**
   *Creates a random weighted graph. The weights will be even distributed between 1 and
   *the maximum edge weight (inclusive).
   *@return a random graph of the specified density
   *@param numberOfVertices the nukmber of vertices
   *@param directed true if the graph is to be directed
   *@param maxWeight the maximum edgeWeight for the Graph.
   *@param density between 0 and 1, the probablity of an edge existing.
   **/
  public static Graph randomWeightedGraph(int numberOfVertices, boolean directed, double density,int maxWeight){
	Graph g = new Graph(numberOfVertices, true, directed);
    for(int i = 0; i<g.getNumberOfVertices(); i++){
      for(int j = 0; j<(directed?g.getNumberOfVertices():i+1); j++){
		if(Math.random()<density){
			g.edgeMatrix[i][j] = (int)(Math.random()*(maxWeight-1))+1;
			if(!directed) g.edgeMatrix[j][i] = g.edgeMatrix[i][j];
		}
      }
    }
    return g;
  }


  /** reads an adjacency matrix from a file and returns it.  The
   * adjacency matrix is assumed to have the following format in
   * the file:
   * n
   * 0 6 0 0 ... 0
   * 0 0 0 3 ... 0
   * ...
   * 1 0 7 0 ... 0
   * where the first line contains an integer that denotes the dimensions
   * of the square matrix of integers that follow, and there are n integers
   * (tab separated) on each of the subsequent lines.
   *@author Du Huynh (modifed by Tim French)
   *@return A graph read fro the file.
   *@param filename the name of the file to be read
   *@param weighted true if the Graph is to be weighted
   *@param directed true if the graph is to be directed
   */
  public static Graph readFile(Alphabet alpha, String filename, boolean weighted, boolean directed) throws Exception{
    String delim = " \t";		// the delimiters (spaces and tabs)
    java.io.BufferedReader in = new java.io.BufferedReader(new java.io.FileReader(filename));
    String s = in.readLine();

    /* read in the number of vertices */
    int n = Integer.parseInt(s);

    Graph g = new Graph(n, weighted, directed);
    for (int i=0; i < n; i++) {
      java.util.StringTokenizer stoken = new java.util.StringTokenizer(in.readLine().trim(), delim);
      for (int j=0; j < n; j++) {
			String subs = stoken.nextToken();
			g.addEdge(i,j,Integer.parseInt(subs));
      }
    }
    for (int i=0; i < n; i++) {
    	String l = in.readLine();
    	// Does the alphabet contain the label
    	if (alpha.contains(l)) {
    		g.addLabel(i, l);
    	}
    	else {
			Exception e = new Exception("Graph label does not belong to the alphabet");
			throw e;
    	}
    }
    in.close();
    return g;
  }

  /**
   *This method produces a representation of the
   *graph that corresponds to the adjacency
   *matrix used by the readFile method.
   *@return a String representation of the graph,
   **/
  public String toString(){
    StringBuffer s = new StringBuffer(getNumberOfVertices()+"\n");
    for (int i = 0; i<numberOfVertices; i++){
    	s.append("\t");
    	s.append(labels[i]);
    }
    s.append("\n");
    for(int i = 0; i<numberOfVertices; i++){
      s.append(labels[i]);
      s.append("\t");
      for(int j = 0; j<numberOfVertices; j++){
		s.append(edgeMatrix[i][j]);
		s.append("\t");
      }
      s.append("\n");
    }
    return s.toString();
  }

}
